import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);
            System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
            System.out.println("递归之后 => " + path);
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] candidates = new int[]{2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> res = solution.combinationSum(candidates, target);
        System.out.println("输出 => " + res);
    }
}

//作者：liweiwei1419
//        链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


//import java.util.ArrayList;
//import java.util.List;
//import java.util.Scanner;
//
////给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
////说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。
//public class Test11_23 {
//    List<Integer> now = new ArrayList<>();
//    List<List<Integer>> all = new ArrayList<>();
//    static int firstTarget;
//    void test(List<Integer> candidates, int target, int len, List<Integer> now){
//        if(target==0){
//            all.add(now);
//        }else if (target>0){
//            for (int i = len; i < candidates.size(); i++) {
//                int num = candidates.get(i);
//                if(target>=num){
//                    now.add(candidates.get(i));
//                    test(candidates,target,len-1,now);}
//                else test(candidates,firstTarget,len-1,now);
//            }
//        }
//    }
//    public static void main(String[] args) {
//        List<Integer> temp = new ArrayList<>();
//        List<Integer> candidates = new ArrayList<>();
//        Scanner sc = new Scanner(System.in);
//        firstTarget = 10;
//        candidates.add(2);
//        candidates.add(4);
//        candidates.add(4);
//        Test11_23 test11_23 = new Test11_23();
//        test11_23.test(candidates, firstTarget , candidates.size(), test11_23.now);
//    }
//}
